#include <cstdio>
#include <algorithm>
using namespace std;
//返回数组A左闭右开区间[x,y)的最大连续和
int maxSum(int* A,int x,int y){
	if(y-x==1){
		return A[x];
	}
	int m=x+(y-x)/2;
	//递归求两边分别的最大和
	int maxm=max(maxSum(A,x,m),maxSum(A,m,y));
	int v,L,R;
	//找到从中间向左延伸的最大和
	v=0;
	L=A[m-1];
	for(int i=m-1;i>=x;i--){
		L=max(L,v+=A[i]);
	}
	//找到从中间向右延伸的最大和
	v=0;
	R=A[m];
	for(int i=m;i<y;i++){
		R=max(R,v+=A[i]);
	}
	//比较是横扩中间的最大和大还是左右分别的最大和大
	return max(maxm,L+R);
}
int main(void){
	int A[]={-5,4,1,6,-4,5,1,3,-9,7,1,-3,4};
	int ans=maxSum(A,0,13);
	printf("%d\n",ans);
	return 0;
}
